#include <iostream>
#include "BinarySearchTree.h"
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
void BST_sort(std::vector<T> &_data)
{
    //cout << "doing BST_sort..." << endl;
    ///用_data里的数据v构建一个二叉树
    BinarySearchTree<T> tr;
    for (int i = 0; i < _data.size(); i++)
        tr.insert(_data[i]);

    ///此时树已有序，只需将树中元素覆盖到_data中
    _data.clear();
    while (!tr.isEmpty())
    {
        T x = tr.findMin();
        tr.remove(x);
        _data.push_back(x);

    }
    //tr.printTree();
}

template <typename T>
void Randomized_BST_sort(std::vector<T> &_data)
{
    ///打乱之后用BST_sort即可
    //cout << "Randomzing..." << endl;
    random_shuffle(_data.begin(),_data.end());
    //for(int i = 0; i < _data.size(); i++)
    //    cout << _data[i] << "\t";
    //cout << endl;
    BST_sort(_data);
}

int main()
{
    ///随机生成一串数据，这里取10个随机的小于64的两位数
    srand((unsigned)time(NULL));
    vector<int> a;
    for(int i = 0; i < 10; i++)
    {
        a.push_back(rand() & 63);
    }

    ///输出这一串未排列的数据
    cout << "There are some random numbers!" << endl;
    for(int i = 0; i < a.size(); i++)
        cout << a[i] << "\t";
    cout << endl;

    ///对这串数据进行排序
    Randomized_BST_sort(a);

    ///输出排好序的a
    cout << "Here is the ordered sequence!" << endl;
    for(int i = 0; i < a.size(); i++)
        cout << a[i] << "\t";
    cout << endl;

    return 0;
}